The present invention relates generally to the processing of data packets in a network processor, and more specifically, to the reassembly of data blocks into the form of a data packet from which they were initially partitioned.
Computer or data networks allow users to share or multiplex resources such as printer servers, routers, file systems, long-distance data trunks, search engine servers and web site servers. Data transmitted through a network is typically segmented into finite portions or blocks. Under some network protocols, the data is segmented into fixed-length cells. For example, in the asynchronous transfer mode (ATM) protocol data is segmented into 53-byte cells, with 5 bytes of each cell designated for a header (also referred to as meta-data) and 48 bytes of each cell designated for the payload or information. Other network protocols, such as the Ethernet protocol, allow data segmentation into variable-length packets. For example, an Ethernet packet has a 14-byte header and a payload size that can vary from 64 bytes to 1,500 bytes.
Processing fixed-length packets, such as ATM cells, through a network processor, such as a switch, is easier than processing variable-length packets. Since the length of each fixed-length packet is known, the propagation time through a switch is predictable and it is therefore easier to arrange for the packets to pass through the switch one after another in a pipelined fashion, i.e., the packets are transferred over a single data path in series with no gap between the adjacent packets.
In contrast to the fixed length packets, the time required to process variable-length packets through a switch or other network processors varies. Thus it is difficult to pipeline variable-length packets. Further, the variable-length packet creates system timing uncertainties as it is difficult to properly time certain events, such as scheduling data arbitration and the retrieval of packets from buffers, when the processing time for the previous packet is not known a priori.
To make processing of variable-length packets more manageable, variable-length packets are segmented into fixed-length blocks that pass through a switch fabric or other network processor in a known and fixed time. The fixed-length blocks have a header portion and a payload portion and the number of fixed-length blocks per packet is directly related to the size of the packet. The fixed-length blocks are used only internal to the network processor and are maintained in order during processing. The blocks are reassembled back into packet form prior to transmittal to the downstream network processor.
Variable length data packets may also be segmented into data blocks for the purpose of applying error control functionality to the blocks. In this way, not only will a concatenated sequence of data blocks be protected against errors, but each block within the sequence will also be protected.
The present invention describes a method and apparatus for the reassembly of data blocks back into the packet (or PDU, packet data unit) from which they were previously segmented for ease in processing through a network processor, such as a network switch. Prior to beginning the reassembly process, each block is assigned a queue identifier that is uniquely associated with the packet from which the blocks were partitioned and into which they will be reassembled. Once the first block of a packet is assigned a queue identifier, that queue identifier is rendered unavailable for assignment until the reassembly process for that packet is complete. A packet identifier is assigned to each packet, as well as a start-of-packet and an end-of-packet identifier that are useful during packet processing by downstream network processors. The packet reassembly process is terminated when the block carrying an end-of-field identifier, indicating that it is the last block for the packet, is added to the reassembled packet. According to the present invention, packets of any length and protocol can be reassembled from their constituent blocks.